use std::collections::HashMap;

struct Trie {
    children: HashMap<char, Trie>,
    value: Option<String>,
}

impl Trie {
    fn new() -> Self {
        Trie {
            children: HashMap::new(),
            value: None,
        }
    }

    fn insert(&mut self, key: &str, value: String) {
        let mut node = self;
        for c in key.chars() {
            node = node.children.entry(c).or_insert_with(Trie::new);
        }
        node.value = Some(value);
    }

    fn lookup(&self, key: &str) -> Option<&String> {
        let mut node = self;
        for c in key.chars() {
            match node.children.get(&c) {
                Some(next_node) => node = next_node,
                None => return None,
            }
        }
        node.value.as_ref()
    }

    fn remove(&mut self, key: &str) -> bool {
        let mut path: Vec<(&char, &mut Trie)> = Vec::new();
        let mut node = self;
        for c in key.chars() {
            match node.children.get_mut(&c) {
                Some(next_node) => {
                    path.push((&c, next_node));
                    node = next_node;
                }
                None => return false,
            }
        }

        if node.value.is_some() {
            node.value.take();
            for (c, parent) in path.iter().rev() {
                if !parent.children[*c].children.is_empty() || parent.children[*c].value.is_some() {
                    break;
                }
                parent.children.remove(c);
            }
            true
        } else {
            false
        }
    }

    fn free(&mut self) {
        self.children.clear();
        self.value.take();
    }
}

fn main() {
    let mut trie = Trie::new();

    // Test insert and lookup
    trie.insert("hello", "world".to_string());
    assert_eq!(trie.lookup("hello"), Some(&"world".to_string()));

    // Test remove
    assert!(trie.remove("hello"));
    assert_eq!(trie.lookup("hello"), None);

    // Test free
    trie.free();
    assert!(trie.children.is_empty());
    assert_eq!(trie.value, None);
}
